package leecode.array.二分查找问题;

/**
 * https://leetcode.cn/problems/find-peak-element/description/
 *
 * 注意这个题需要返回 下标
 *
 *  局部峰值
 */
public class FindPeakElement {

    // log(N) 解法
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int index = 0;
        if (nums.length == 1) {
            return index;
        }
        while (left <= right) {
            int mid = left + (right - left)/2;
            // 需要处理mid是边界的情况，比如测试用例 [2,1]，返回0 ； [1,2]，返回1
            if (((mid > 0 && mid < nums.length - 1 && nums[mid] > nums[mid - 1]
                    && nums[mid] > nums[mid + 1])) || (mid == 0 && nums[mid] > nums[mid + 1]) || (mid == nums.length - 1 && nums[mid] > nums[mid - 1])) {
                return mid;
            } else if (mid < nums.length - 1 && nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return 0;
    }

    // O(n)解法
    public int findPeakElement2(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int max = Integer.MIN_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }

        }
        return index;
    }

}
